<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 统计全 1 子矩形 -->
    <script>
      var numSubmat = function (mat) {
        const row = mat.length
        const col = mat[0].length
        const h = new Array(row).fill(0, 0) // 存放以元素(i,j)结尾所在行连续1的个数
        let res = 0
        for (let j = 0; j < col; j++) {
          let sum = 0 // 遍历到元素(i,j)之前，以元素(i-1,j)为右下角所能构成的矩阵个数
          let stack = [] // 单调栈stack<int[h[i], 栈中比h[i]大的个数]>
          for (let i = 0; i < row; i++) {
            h[i] = mat[i][j] == 1 ? h[i] + 1 : 0 //计算以该元素(i,j)结尾所在行连续1的个数
            let cnt = 0 // 统计比h[i]元素大的个数
            // 如果元素(i,j)对应的h[i] > 栈顶元素对应h[i-1],则所有以元素(i-1,j)为右下角的矩阵拼接元素(i,j)就能形
            //成新的矩阵, 否则需要减去不合格的矩阵
            while (stack.length && stack[stack.length - 1][0] > h[i]) {
              //减去不能参与以(i,j)为右下角构建矩阵的矩阵
              sum -= (stack[stack.length - 1][1] + 1) * (stack[stack.length - 1][0] - h[i])
              cnt += stack[stack.length - 1][1] + 1
              stack.pop()
            }
            sum += h[i] // 举例子: 元素(i, j)对应的h[i] = 4, 那么在以元素(i,j)为右下角的矩阵至少有4个
            res += sum
            stack.push([h[i], cnt])
          }
        }
        return res
      }
      console.log(
        numSubmat([
          [1, 0, 1],
          [1, 1, 0],
          [1, 1, 0]
        ])
      )
    </script>
  </body>
</html>
